/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
void quickSorted(int *nums, int left, int right){
    if (left > right) return;
    int i = left, j = right, temp = nums[left];
    while (i < j){
        while (i < j && temp <= nums[j])
            j--;
        if (i < j)
            nums[i++] = nums[j];
        while (i < j && temp > nums[i])
            i++;
        nums[j--] = nums[i];
    }
    nums[i] = temp;
    quickSorted(nums, left, i - 1);
    quickSorted(nums, i + 1, right);
}

struct ListNode* sortInList(struct ListNode* head ) {
    int length = 0;
    struct ListNode *cur = head;
    while(cur){
        length++;
        cur = cur->next;
    }
    int *nums = (int*)malloc(sizeof(int) * length);
    cur = head;
    int index = 0;
    //链表转数组
    while (cur){
        nums[index++] = cur->val;
        cur = cur->next;
    }
    quickSorted(nums, 0, length - 1);
    cur = head;
    int i = 0;
    //数组重新转链表
    while (cur){
        cur->val = nums[i++];
        cur = cur->next;
    }
    return head;
}